;====================== ADT implementation ======================================================

;;;  1. Signature: (make-relation <Name> <Schema> <Data>) 
;;;  2. Type: Symbol*List(Symbol)*List(List)-> Relation 
;;;  3. Purpose: Constructor. 'data' is all the tuples in the relation 
;;;  4. Example:  
;;; (define employee  
;;;  (make-relation 'Employee  
;;;               '(ID name department age salary)  
;;;               '((4356291 moshe IE 32 10000) 
;;;                 (6547209 rina Biology 45 15000) 
;;;             (9027546 rina IE 32 25000)))) 
;;; creates Employee relation as described above. 
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (make-relation rel-name rel-schema rel-data) 
  (list rel-name rel-schema rel-data))

;;;;;;;;;;;;;;;;;;;
(define (relation? x)
  (and (list? x)
       (= (length x) 3)
       (list? (relation-schema x))
       (list? (relation-data x))
       )
)

;;;  1. Signature: (relation-name <Relation>) 
;;;  2. Type: Relation->Symbol 
;;;  3. Purpose: Selector. returns the name of the given relation. 
;;;  4. Example: (relation-name employee) returns Employee. 
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests:  
(define (relation-name relation) 
  (car relation))

;;;  1. Signature: (relation-schema <Relation>) 
;;;  2. Type: Relation->List(Symbol) 
;;;  3. Purpose: returns the list of attribute names in the relation. 
;;;  4. Example: (relation-schema employee) returns (ID name department age salary). 
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (relation-schema relation) 
  (cadr relation))

;;;  1. Signature: (relation-data <Relation>) 
;;;  2. Type: Relation->List(List) 
;;;  3. Purpose: returns the set of tuples in the relation. 
;;;  4. Example: (relation-data employee) returns  
;;;   ((4356291 moshe IE 32 10000) (6547209 rina Biology 45 15000) (9027546 rina IE 32 25000)). 
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (relation-data relation) 
  (caddr relation)) 

;;;  1. Signature: (relation-size <Relation>) 
;;;  2. Type: Relation->Number 
;;;  3. Purpose: returns the number of tuples in the relation. 
;;;  4. Example: (relation-size employee) returns 3. 
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (relation-size relation) 
  (length (relation-data relation)))

;;;  1. Signature: (relation-attribute-values <Attribute List> <Relation> <Tuple>) 
;;;  2. Type: List(Symbol)*Relation*List->List 
;;;  3. Purpose: return the values of the attribute names in the given tuple of the  
;;; relation according to their locations in the relation's schema. 
;;;  4. Example: (relation-attribute-values  '(ID age )  employee  '(4356291 moshe IE 32 10000)) returns 
;;;  (4356291 32). 
;;;  5. Pre-conditions: <Attribute List> is an ordered sub-list of <Relation>
;;; schema. 
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (relation-attribute-values attributes relation tuple) 
  (cond ((null? attributes) '())
        (else (cons (list-ref tuple (index-of (car attributes) (relation-schema relation)))
                    (relation-attribute-values (cdr attributes) relation tuple)))))
 
;;;  1. Signature: (relation-map-data <Function> <Relation>) 
;;;  2. Type: [List(T1)->T2]*Relation->List(T2)  
;;;  3. Purpose: returns a list of the results of applying a given 1-ary function 
;;; on each tuple in the data of a given relation. 
;;; Eliminate duplicates from the result list.  
;;;  4. Example:  
;;;  Find employee names: 
;;;  (relation-map-data (lambda (tuple) (cadr tuple)) employee) returns (moshe rina). 
;;;  Find employee department and ages: 
;;;  (relation-map-data (lambda (tuple) (list (caddr tuple) (cadddr tuple))) employee) returns  
;;;  ((Biology 45) (IE 32)). 
;;;  5. Pre-conditions: <Function> accepts the tuples of the relation as input. 
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (relation-map-data function relation) 
  (map function (relation-data relation)))


;=============================== Client level =============================================================

;;; 1. Signature: (Project <Relation> <Partial Schema>)
;;; 2. Type: Relation *List(Symbol)->Relation
;;; 3. Purpose: Return an anonymous relation with a partial schema (attribute list)
;;; of the given relation. It contains these attributes values from tuples of the
;;; given relation, without duplicate tuples.
;;; 4. Example:
;;; >(define project-result (Project employee '( department age )))
;;; >(relation-name project-result)
;;; anonymous
;;; >(relation-schema project-result)
;;; (department age)
;;; >(relation-data project-result)
;;; ((Biology 45) (IE 32))
;;; 5. Pre-conditions: <Attribute Name List> is an ordered sub-list of <Relation>’s
;;; schema.
;;; 6. Post-conditions:
;;; 7. Tests:
(define (Project relation partial-schema)
(make-relation 'anonymous 
               partial-schema 
               (relation-map-data
                (lambda(tuple)
                  (relation-attribute-values partial-schema relation tuple))
                relation)))

;;; 1. Signature: (Select <Relation> <Attribute name> <Criteria function>)
;;; 2. Type: Relation*Symbol*[T1->Boolean]->Relation
;;; 3. Purpose: Return a relation with same schema of given relation, with
;;; tuples of given relation, for which the value of the given attribute holds
;;; for the given criteria predicate procedure. Hint: use filter.
;;; 4. Example:
;;; >(define select-result (Select employee 'salary (lambda (s) (< s 25000))))
;;; >(relation-name select-result)
;;; anonymous
;;; >(relation-schema select-result)
;;; (ID name department age salary)
;;; >(relation-data select-result)
;;; ((4356291 moshe IE 32 10000) (6547209 rina Biology 45 15000))
;;; 5. Pre-conditions: <Attribute name> is a member of <Relation>’s schema.
;;; 6. Post-conditions:
;;; 7. Tests:
(define (select relation attribute criteria)
    (make-relation 
     'anonymous 
     (relation-schema relation) 
     (filter 
      (lambda(tuple)
        (criteria(car(relation-attribute-values (list attribute) relation tuple)))) 
      (relation-data relation)))) 
                                          
;;;  1. Signature: (Product <Relation 1> <Relation 2>) 
;;;  2. Type: Relation*Relation->Relation 
;;;  3. Purpose: Create a relation which is a product of the given relations.
;;; Hint: Use ‘append’ and nested calls to ‘map’ that run over the data of the 2  
;;; relations. 
;;;  4. Example:  
;;; 
;;;>(define product-result (Product employee dept-building)) 
;;;  >(relation-name product-result) 
;;;  anonymous 
;;;  >(relation-schema product-result) 
;;;   (ID name department age salary department building) 
;;;  >(relation-data product-result) 
;;; ; results in 9 tuples.  
;;;  ; Sanity check relation-attribute-values: 
;; >( relation-attribute-values '(department)  
;;; 
;;;                              (Product employee dept-building)  
;;;                              '(4356291 moshe IE 32 10000 IE B25)) 
;;;   (IE) 
;;;  >( relation-attribute-values '(department department)  
;;;                              (Product employee dept-building)  
;;;                              '(4356291 moshe IE 32 10000 Biology B75)) 
;;;   (IE  Biology) 
;;;  >( relation-attribute-values '(department age department)  
;;;                              (Product employee dept-building)  
;;;                             '(4356291 moshe IE 32 10000 Biology B75)) 
;;;   (IE 32 Biology)  
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests:  
(define (Product relation1 relation2) 
  (make-relation 
   'anonymous                        
   (append (relation-schema relation1) (relation-schema relation2)) 
   (accumulate append 
               () 
               (map (lambda (i) 
                      (map (lambda (j)(append i j)) (relation-data relation2)))
                    (relation-data relation1)))))
                         
;;;  1. Signature: (Natural-join <Relation 1> <Relation 2> <Attribute name>)
;;;  2. Type: Relation*Relation*Symbol->Relation
;;;  3. Purpose: returns a relation with a unified schema, with the given
;;; attribute appearing exactly once. The relation contains the tuples
;;; containing values of tuples from both given relations that have identical
;;; values of the given attribute. Hint: One way to perform natural-join is by
;;; applying Product, then filtering the required tuples, then applying Project.
;;;  4. Example:  
;;;  5. Pre-conditions:  
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (Natural-join relation1 relation2 attribute)  
(let ((attribute-first-index (index-of attribute (relation-schema relation1)))
      (attribute-second-index (+(index-of attribute (relation-schema relation2)) (length (relation-schema relation1)))))
  (Project
   (make-relation 
    'anonymous                        
    (append (relation-schema relation1) (relation-schema relation2))
    (filter (lambda(tuple) (equal? (list-ref tuple attribute-first-index) (list-ref tuple attribute-second-index))) 
            (relation-data (Product relation1 relation2))))
   (append (relation-schema relation1) (filter (lambda(att) (not (equal? att attribute))) (relation-schema relation2)))
   )))
    
;;;  1. Signature: (Aggregate <Function> <Relation> <Attribute name>) 
;;;  2. Type: [T1*T1->T2]*Relation*Symbol->T2 
;;;  3. Purpose: Aggregate a function over the an attribute values in a  
;;; relation. Can be implemented using accumulate.  
;;;  4. Example: 
;;;      (Aggregate + employee 'salary) returns 50000. 
;;;  5. Pre-conditions: The relation has at least one tuple. <Attribute name> is  
;;; a member of <Relation>’s schema.  
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (Aggregate function relation attribute) 
  (accumulate function 0
             (accumulate append () 
                         (relation-data (Project relation (list attribute))))))

;;;  1. Signature: (Aggregate-pre-condition-tes <Function> <Relation> <Attribute name>) 
;;;  2. Type: T*T*T->Boolean 
;;;  3. Purpose: assert the pre-conditions for the aggregate function
;;;  4. Example: 
;;;      (Aggregate-pre-condition-test + 'Employee attribute)
;;;  5. Pre-conditions: 
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (Aggregate-pre-condition-test function relation attribute)
  (and ((relation? relation))
       ((symbol? attribute))
       ((procedure? function))
       (member? attribue (relation-schema relation))
       )
  )
;  ( cond ((not (procedure? function)) #f)
;       ((not (list? relation)) #f)
;       ((not (symbol? attribute)) #f)
;       ((null? (relation-data relation)) #f)
;       ((< (index-of attribute (relation-schema relation)) 0) #f)
;       ( else #t)))


;=================================Question 4======================================================
;If we change the implementation of Relation ADT, to be a procedural one, the client relational algebra 
;procedures would not need to be changed, because the ADT is abstract and implements a constant interface.
;the ADT supplies only getters and setters for the relation algebra and does not reveals its implementation.
;Therefore if we would like to change the ADT, we MUST keep the same interface (meaning the same getters and setters
;with the same results) but the inner implemation of the ADT can be changed according to our needs, because anyone
;that want to use this ADT can only access it by the interface

;================================help functions ===================================
;;;  1. Signature: index-of (x indexed-list)
;;;  2. Type: T*List[T] --> Number
;;;  3. Purpose: find the index of a parameter in the list
;;;  4. Example: (index-of 'age '(name age location))
;;;  5. Pre-conditions: the list length is less than 100000000.
;;;  6. Post-conditions: if the parameter is a member of list the return value > 0, else the return value is < 0 
;;;  7. Tests: (index-of 'age '(name age location)) ==> 2
;;;            (index-of 'not-here '(name age location)) ==> negative value
;(define (index-of x indexed-list)
;  (cond 
;    ((null? indexed-list) -100000000)
;    ((equal? (car indexed-list) x) 0)
;    (else (+ 1 (index-of x (cdr indexed-list))))))

(define (index-of obj indexed-list)
  (letrec ((index-of-iter 
            (lambda (ls bypassed) 
              (cond 
                ((null? ls) -1)
                ((equal? obj (car ls)) bypassed)
                (else (index-of-iter (cdr ls) (+ bypassed 1)))))))
    (index-of-iter indexed-list 0)))

  
  

; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Auxilary procedures ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
;;; this part includes function that was presented on class and does not hold contracts
;;;  1. Signature: 
;;;  2. Type: 
;;;  3. Purpose:
;;;  4. Example: 
;;;  5. Pre-conditions: 
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

;;;  1. Signature: 
;;;  2. Type: 
;;;  3. Purpose:
;;;  4. Example: 
;;;  5. Pre-conditions: 
;;;  6. Post-conditions:  
;;;  7. Tests: 
(define (filter predicate sequence)
  (cond ((null? sequence) ())
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

;;;  1. Signature: 
;;;  2. Type: 
;;;  3. Purpose:
;;;  4. Example: 
;;;  5. Pre-conditions: 
;;;  6. Post-conditions:  
;;;  7. Tests: 
;(define (length items)  
;     (if (null? items)  
;       0  
;       (+ 1 (length (cdr items))))) 



(define relation (make-relation 'Employee  
              '(id name department age salary)  
              '((4356291 moshe ie 32 10000) 
                 (6547209 rina biology 45 15000) 
                 (9027546 rina ie 32 25000))) )

(define relation2 (make-relation 'Job  
              '(place salary)  
              '((Netanya 10000) 
                 (TA 15000) 
                 (Jer 25000))) )



(define ans (select relation 'salary (lambda (s) (< s 25000))))
ans
